package com.example.algorithm.sorts;

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    public static void main(String[] args) {
        int[] nums = {3,5,7,4,2,9,1,3};
        quickSort(nums, 0, nums.length -1);

        for (int num : nums) {
            System.out.print(num + ",");
        }

    }

    public static void quickSort(int[] nums, int begin, int end) {
        if ((end - begin) < 2 )
            return;

        int pivotIndex = getPivotIndex(nums, begin, end);

        quickSort(nums, begin, pivotIndex);
        quickSort(nums, pivotIndex + 1, end);
    }

    private static int getPivotIndex(int[] nums, int begin, int end) {
        System.out.println("本次计算轴点的范围为: " + begin + "~" + end);

        // 用一个从begin到end的随机值与begin的值交换，主要是为了避免最坏的情况发生
        int random = new Random().nextInt(end - begin) + begin;
        // 用于临时存储轴点元素的值
        int pivot = nums[random];
        nums[random] = nums[begin];
        nums[begin] = pivot;

        // 当begin ==end时说明本次的轴点已经找到，才会退出循环
        while (begin < end) {
            // 这个循环控制的是从右往左遍历，一旦反向就要退出循环
            while (begin < end) {
                if (pivot < nums[end]) { // 右边元素 > 轴点元素
                    --end;
                } else {
                    // 一旦begin,end指向的元素进行了替换换意味着换方向了，就要退出本次循环
                    nums[begin] = nums[end];
                    ++begin;
                    break;
                }

            }

            // 这个循环控制的是从左往右遍历，一旦反向就要退出循环
            while (begin < end) {
                if (nums[begin] < pivot) { // 左边元素 < 轴点元素
                    ++begin;
                } else {
                    nums[end] = nums[begin];
                    --end;
                    break;
                }
            }
        }

        // 将轴点元素放到对应的位置上(每进行一次，该轴点元素的最终位置就被确定)
        nums[begin] = pivot;
        System.out.println("排序结果为:");
        System.out.println(Arrays.toString(nums));
        System.out.println("轴点元素为: " + pivot + "，计算完后轴点索引为:" + begin);
        System.out.println("-------------------");
        return begin;
    }
}
